'''
1. https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
2. https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
'''
from c06_tree.utils import TreeNode


class Solution:

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if (root is None) or (root == p) or (root == q):
            return root
        left_find = self.lowestCommonAncestor(root.left, p, q)
        right_find = self.lowestCommonAncestor(root.right, p, q)

        # 如果在左右分别找到了p,q。返回自己是最近的祖先
        if left_find and right_find:
            return root
        # 如果左右都没有，就跟当前子树无关
        if left_find is None and right_find is None:
            return None
        # 如果只有一个
        #   1. 已经找到了最近公公祖先
        #   2. 只找到了p或q，但是是p包含q，或q包含p的结构
        return left_find if left_find else right_find

    def lowestCommonAncestor1(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def find(root, p, q) -> (bool, bool, TreeNode):
            if root is None: return (False, False, None)
            info1 = find(root.left, p, q)
            info2 = find(root.right, p, q)
            findP = info1[0] or info2[0] or root == p
            findQ = info1[1] or info2[1] or root == q
            ans = info1[2] or info2[2] or (root if (findP and findQ) else None)
            return (findP, findQ, ans)
        return find(root, p, q)[2]

    def lowestCommonAncestor2(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 1. 如果p,q 一左一右，当前就是最近祖先
        # 2. 如果p,q在一侧,去那一侧寻找
        # 3. 这种情况下如果遇到了p或q，那就说明他就是最近祖先
        while root != p and root != q:
            if min(p.val, q.val) < root.val < max(p.val, q.val):
                break
            root = root.left if max(p.val, q.val) < root.val else root.right
        return root

